# 分块 O(N^3/2)
class Solution:
    def numOfUnplacedFruits(self, fruits: List[int], baskets: List[int]) -> int:
        n = len(baskets)
        m = int(math.sqrt(n))
        section = (n + m - 1) // m # 向上取整，n//m向下取整不能整除时最后一块会缺失导致越界错误
        count = 0
        max_V = [0] * section

        for i in range(n):
            max_V[i//m] = max(max_V[i // m], baskets[i])

        for fruit in fruits:
            unset = 1
            for sec in range(section):
                if max_V[sec] < fruit: #该分块内最大值小于水果数量，一定不成立，跳过
                    continue
                choose = 0 # 确保一个分块内有一个被选到时能跳出该分块
                max_V[sec] = 0
                for i in range(m):
                    pos = sec * m + i 
                    if pos < n and baskets[pos] >= fruit and not choose:# 不越界，容量OK，没被选过
                        baskets[pos] = 0 # 选过
                        choose = 1
                    if pos < n :
                        max_V[sec] = max(max_V[sec], baskets[pos]) # 更新现在的最大值
                unset = 0
                break
            count += unset
        return count


        
# 线段树 + 二分 O(Nlogn)
class SegmentTree:
    def __init__(self, a: List[int]):
        n = len(a)
        self.max = [0] * (2 << (n - 1).bit_length())
        self.build(a, 1, 0, n - 1)

    def maintain(self, o: int):
        self.max[o] = max(self.max[o * 2], self.max[o * 2 + 1])

    # 初始化线段树
    def build(self, a: List[int], o: int, l: int, r: int):
        if l == r:
            self.max[o] = a[l]
            return
        m = (l + r) // 2
        self.build(a, o * 2, l, m)
        self.build(a, o * 2 + 1, m + 1, r)
        self.maintain(o)

    # 找区间内的第一个 >= x 的数，并更新为 -1，返回这个数的下标（没有则返回 -1）
    def find_first_and_update(self, o: int, l: int, r: int, x: int) -> int:
        if self.max[o] < x:  # 区间没有 >= x 的数
            return -1
        if l == r:
            self.max[o] = -1  # 更新为 -1，表示不能放水果
            return l
        m = (l + r) // 2
        i = self.find_first_and_update(o * 2, l, m, x)  # 先递归左子树
        if i < 0:  # 左子树没找到
            i = self.find_first_and_update(o * 2 + 1, m + 1, r, x)  # 再递归右子树
        self.maintain(o)
        return i


class Solution:
    def numOfUnplacedFruits(self, fruits: List[int], baskets: List[int]) -> int:
        t = SegmentTree(baskets)
        n = len(baskets)
        ans = 0
        for x in fruits:
            if t.find_first_and_update(1, 0, n - 1, x) < 0:
                ans += 1
        return ans

